    /******************************************************************************
 *  Date:
 *      March 2011
 *
 *  Authors:
 *      Tomasz Jankowski 171073
 * 		Marcin Wojciechowski, 181057
 *
 *  Puprose:
 *      An academic project on Univercity of technologi in Wroclaw.
 *
 ******************************************************************************/

#include <tr1/random>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <list>
#include <ctime>
#include <limits.h>
#include <sys/time.h>

#include "vector.hpp"
#include "heap.hpp"
#include "graph_generator.hpp"

using namespace std;
using namespace std::tr1;

Graph::Graph (unsigned int nodes,
              unsigned int edges) :
    nodes (nodes),
    edges (edges)
{
    // ...
}

IncidenceMatrix::IncidenceMatrix (unsigned int nodes,
                                  unsigned int edges) :
    Graph (nodes, edges),
    matrix (new int* [nodes])
{
    unsigned int node (0);
    unsigned int edge (0);
    
    for (node = 0; node < nodes; node++)
    {
        this->matrix [node] = new int [edges];
        
        for (edge = 0; edge < this->edges; edge++)
        {
            this->matrix [node][edge] = 0;
        }
    }
}

IncidenceMatrix::~IncidenceMatrix (void)
{
    unsigned int node (0);

    for (node = 0; node < this->nodes; node++)
    {
        delete [] this->matrix [node];
    }
    
    delete [] this->matrix;
}

void IncidenceMatrix::print (void)
{
    unsigned int node (0);
    unsigned int edge (0);
    
    for (node = 0; node < this->nodes; node++)
    {
        for (edge = 0; edge < this->edges; edge++)
        {
            printf (" %3d ", this->matrix [node][edge]);;
        }
        
        printf ("\n");
    }
}

bool IncidenceMatrix::check_nodes (unsigned int begin_node,
                                   unsigned int end_node)
{
    unsigned int edge (0);
    
    // Nie ma petli zwrotnych
    if (begin_node == end_node)
    {
        return false;
    }
    
    return true;
}

OrientedIncidenceMatrix::OrientedIncidenceMatrix (unsigned int nodes,
                                                  unsigned int edges) :
    IncidenceMatrix (nodes, edges)
{
    // ...
}

void OrientedIncidenceMatrix::generate (unsigned int minimum_edge_weight,
                                        unsigned int maximum_edge_weight)
{
    mt19937                   engine;
    uniform_int<unsigned int> node_generator (0, this->nodes - 1);
    uniform_int<unsigned int> edge_weight_generator (minimum_edge_weight, maximum_edge_weight);
    unsigned int              edge (0);
    unsigned int              edge_weight (0);
    unsigned int              begin_node (0);
    unsigned int              tmp_node (0);
    unsigned int              end_node (0);
    bool                      status (false);
    
    for (tmp_node = 0; tmp_node < this->nodes - 1; tmp_node++)
    {
        edge_weight = edge_weight_generator (engine);  
        
        this->matrix [tmp_node][tmp_node] = edge_weight;
        this->matrix [tmp_node + 1][tmp_node] = -(edge_weight);
    }
    
    // Najpierw losujemy graf spojny
    for (edge = this->nodes - 1; edge < this->edges; edge++)
    {
        // Losujemy poczatkowy wierzcholek i wage krawedzi
        begin_node = node_generator (engine);      
        edge_weight = edge_weight_generator (engine);    
        
        // Dobieramy koncowy wierzcholek krawedzi do skutku
        do
        { 
            end_node = node_generator (engine);   
            status = this->check_nodes (begin_node, end_node);
        }
        while (status == false);
        
        this->matrix [begin_node][edge] = edge_weight;
        this->matrix [end_node][edge] = -(edge_weight);
    }
}

void OrientedIncidenceMatrix::find_shortest_path_dijkstra (unsigned int source_node)
{
    Vector<unsigned int>                  distance (this->nodes);
    Heap<unsigned int, unsigned int>      queue (this->nodes, this->nodes);
    std::pair<unsigned int, unsigned int> current_node;
    unsigned int                          i (0);
    unsigned int                          tmp_node (0);
    unsigned int                          tmp_edge (0);
    timeval                               start_time;
    timeval                               finish_time;
    
    gettimeofday (&start_time, NULL);
    
    // Inicjalizacja struktur
    for (i = 0; i < this->nodes; i++)
    {
        distance [i] = UINT_MAX;
        queue [i].first = UINT_MAX;
        queue [i].second = i;
    }
    
    queue [source_node].first = 0;
    distance [source_node] = 0;
    
    // Wlasciwy algorytm
    while (queue.size () != 0)
    {
        // Znajdz wierzcholek z najnizsza waga     
        current_node = queue.extract_min ();
        if (current_node.first == UINT_MAX)
        {
            continue;
        }
        
        // Aktualizujemy informacje o sciezce do nastepnikow zgodnie z regula relaksacji
        // Szukamy krawedzi wychodzacych z wierzcholka 'current_node'. Kazda taka
        // krawedz ma wartosc dodatnia (zgdnie z Cormenem)
        for (tmp_edge = 0; tmp_edge < this->edges; tmp_edge++)
        {            
            if (this->matrix [current_node.second][tmp_edge] > 0)
            {
                // Mamy krawedz, teraz szukamy jej koncowego wierzcholka, ktory musi 
                // miec wartosc ujemna.
                for (tmp_node = 0; tmp_node < this->nodes; tmp_node++)
                {
                    if (this->matrix [tmp_node][tmp_edge] < 0)
                    {
                        // Przeprowadzamy relaksacje
                        if (distance [tmp_node] > distance [current_node.second] + this->matrix [current_node.second][tmp_edge] ||
                            distance [tmp_node] == UINT_MAX)
                        {
                            distance [tmp_node] = distance [current_node.second] + this->matrix [current_node.second][tmp_edge];
                        }
                    }
                }
            }
        }
        
        // Auktualizujemy kolejke
        for (i = 0; i < queue.size (); i++)
        {
            queue.decrease_key (i, distance [queue [i].second]);
        }

#ifdef VERBOSE        
        // Wyswietl kroki
        for (i = 0; i < this->nodes; i++)
        {
            printf ("%2d ", distance [i]);
        }    
        
        printf ("\n");
#endif // VERBOSE         
    }
    
    gettimeofday (&finish_time, NULL);

#ifdef VERBOSE      
    printf ("\tCzas wykonania: %d nan\n", (finish_time.tv_sec - start_time.tv_sec));
#else
    printf ("%lf\n", (finish_time.tv_sec - start_time.tv_sec) + (finish_time.tv_usec - start_time.tv_usec) / 1000000.0);
#endif // VERBOSE
}

void OrientedIncidenceMatrix::find_shortest_path_bellman_ford (unsigned int source_node)
{
    Vector<unsigned int> distance (this->nodes);
    unsigned int         i (0);
    unsigned int         tmp_node (0);
    unsigned int         tmp_destination_node (0);
    unsigned int         tmp_edge (0);
    unsigned int         u_node (0);
    unsigned int         v_node (0);
    timeval              start_time;
    timeval              finish_time;
    
    gettimeofday (&start_time, NULL);
    
    // Inicjalizacja struktur
    for (i = 0; i < this->nodes; i++)
    {
        distance [i] = UINT_MAX;
    }
    
    distance [source_node] = 0;
         
    for (tmp_node = 0; tmp_node < this->nodes; tmp_node++)
    { 
        for (tmp_edge = 0; tmp_edge < this->edges; tmp_edge++)
        {  
            if (this->matrix [tmp_node][tmp_edge] > 0)
            {
                for (tmp_destination_node = 0; tmp_destination_node < this->nodes; tmp_destination_node++)
                {
                    if (this->matrix [tmp_destination_node][tmp_edge] < 0)
                    {
                        // Przeprowadzamy relaksacje
                        if (distance [tmp_destination_node] > distance [tmp_node] + this->matrix [tmp_node][tmp_edge] && distance [tmp_node] != UINT_MAX)
                        {
                            distance [tmp_destination_node] = distance [tmp_node] + this->matrix [tmp_node][tmp_edge];
                        }
                        
                        break;
                    }
                }
            }
        }
#ifdef VERBOSE        
        // Wyswietl kroki
        for (i = 0; i < this->nodes; i++)
        {
            printf ("%2d ", distance [i]);
        }
              
        printf ("\n");
#endif // VERBOSE 
    }
    
    for (tmp_edge = 0; tmp_edge < this->edges; tmp_edge++)
    {  
        for (tmp_node = 0; tmp_node < this->nodes; tmp_node++)
        {
            if (this->matrix [tmp_node][tmp_edge] > 0)
            {
                u_node = tmp_node;
            }
            if (this->matrix [tmp_node][tmp_edge] < 0)
            {
                v_node = tmp_node;
            }
        }
        
        if ((distance [v_node] > distance [u_node] + this->matrix [u_node][tmp_edge]) && distance [v_node] != UINT_MAX && distance [u_node] != UINT_MAX)
        {
#ifdef VERBOSE         
            printf ("Blad\n");
#endif // VERBOSE             
        }
    }
    
    gettimeofday (&finish_time, NULL);

#ifdef VERBOSE      
    printf ("\tCzas wykonania: %d sekund\n", (finish_time.tv_sec - start_time.tv_sec));
#else
    printf ("%lf\n", (finish_time.tv_sec - start_time.tv_sec) + (finish_time.tv_usec - start_time.tv_usec) / 1000000.0);
#endif // VERBOSE
}

UnorientedIncidenceMatrix::UnorientedIncidenceMatrix (unsigned int nodes,
                                                      unsigned int edges) :
    IncidenceMatrix (nodes, edges)
{
    // ...
}

void UnorientedIncidenceMatrix::generate (unsigned int minimum_edge_weight,
                                          unsigned int maximum_edge_weight)
{
    mt19937                               engine;
    uniform_int<unsigned int>             node_generator (0, this->nodes - 1);
    uniform_int<unsigned int>             edge_weight_generator (minimum_edge_weight, maximum_edge_weight);
    unsigned int                          edge (0);
    unsigned int                          edge_weight (0);
    unsigned int                          begin_node (0);
    unsigned int                          tmp_node (0);
    unsigned int                          end_node (0);
    bool                                  status (false);
    
    for (tmp_node = 0; tmp_node < this->nodes - 1; tmp_node++)
    {
        edge_weight = edge_weight_generator (engine);  
        
        this->matrix [tmp_node][tmp_node] = edge_weight;
        this->matrix [tmp_node + 1][tmp_node] = edge_weight;
    }
    
    // Najpierw losujemy graf spojny
    for (edge = this->nodes - 1; edge < this->edges; edge++)
    {
        // Losujemy poczatkowy wierzcholek i wage krawedzi
        begin_node = node_generator (engine);      
        edge_weight = edge_weight_generator (engine);    
        
        // Dobieramy koncowy wierzcholek krawedzi do skutku
        do
        { 
            end_node = node_generator (engine);   
            status = this->check_nodes (begin_node, end_node);
        }
        while (status == false);
        
        this->matrix [begin_node][edge] = edge_weight;
        this->matrix [end_node][edge] = edge_weight;
    }
}

UnorientedIncidenceMatrix UnorientedIncidenceMatrix::get_spanning_tree_prim (void)
{
    UnorientedIncidenceMatrix wynik(nodes,edges);
    wagi *krawedzie = new wagi [edges];
    bool *kolejka = new bool [nodes];
    for(int i = 0;i < nodes; i++)
		kolejka[i] = false;
		
	timeval  start_time;
    timeval  finish_time;
    
    gettimeofday (&start_time, NULL);
		
     // Szukamy wag krawędzi z macierzy incydencji  
    for(int i = 0; i < edges;i++)
    {
		bool drugi = false;
		for(int j = 0; j < nodes; j++)
			{
				if(this->matrix[j][i]!=0)
				{
					if(!drugi)
					{
						krawedzie[i].waga = this->matrix[j][i];
						krawedzie[i].krawedz = i;
						krawedzie[i].wierzcholek_pocz = j;
						drugi = true;
					}
					else
					{
						krawedzie[i].wierzcholek_koniec = j;
						drugi = false;
						break;
					}
				}
			}
	}
	sortowanie(krawedzie,0,edges);
	int *korzen = new int [nodes];
	int *nastepny = new int [nodes];
	for(int i = 0;i<nodes;i++)
	{
		korzen[i] = nastepny[i] = i;
	}
	kolejka[krawedzie[0].wierzcholek_pocz] = true;
	kolejka[krawedzie[0].wierzcholek_koniec] = true;
	for(int i = 0; i < nodes-1; i++)
	{
		for(int j = edges-1; j>=0;j--)
		{
			if((korzen[krawedzie[j].wierzcholek_pocz] != korzen[krawedzie[j].wierzcholek_koniec]) &&
				(kolejka[krawedzie[j].wierzcholek_pocz] || kolejka[krawedzie[j].wierzcholek_koniec]))
				{
					int temp;
					int pomoc = korzen[krawedzie[j].wierzcholek_pocz];
					korzen[pomoc] = korzen[krawedzie[j].wierzcholek_koniec];
					for(int k = nastepny[pomoc];k!=pomoc;k=nastepny[k])
					{
						korzen[k] = korzen[krawedzie[j].wierzcholek_koniec];
					}
					temp = nastepny[pomoc];
					nastepny[pomoc] = nastepny[korzen[krawedzie[j].wierzcholek_koniec]];
					nastepny[korzen[krawedzie[j].wierzcholek_koniec]] = temp;
					//dodajkraw
					#ifdef VERBOSE
					for(int jajo = 0; jajo < nodes; jajo++)
					{
						wynik.matrix[jajo][krawedzie[j].krawedz] = matrix[jajo][krawedzie[j].krawedz];
					}
					#endif //VERBOSE
					kolejka[krawedzie[j].wierzcholek_pocz] = true;
					kolejka[krawedzie[j].wierzcholek_koniec] = true;
					break;
				}
		}
	}
	
	gettimeofday (&finish_time, NULL);
#ifdef VERBOSE      
    printf ("\tCzas wykonania: %d sekund\n", (finish_time.tv_sec - start_time.tv_sec));
#else
    printf ("%lf\n", (finish_time.tv_sec - start_time.tv_sec) + (finish_time.tv_usec - start_time.tv_usec) / 1000000.0);
#endif // VERBOSE

#ifdef VERBOSE    
	wynik.print();
#endif // VERBOSE 
	delete [] korzen;
	delete [] nastepny;
    delete [] krawedzie;
    delete [] kolejka;
    return wynik;
}
	
void UnorientedIncidenceMatrix::sortowanie(wagi tab[], int lewy, int prawy)
{
if(lewy<prawy)
	{
		int m = lewy;
		for(int i = lewy+1; i <= prawy; i++)
				if(tab[i].waga > tab[lewy].waga)
				{
					wagi kopia;
					kopia = tab[i];
					tab[i] = tab[lewy];
					tab[lewy] = kopia;
				}
		wagi kopia;
		kopia = tab[m];
		tab[m] = tab[lewy];
		tab[lewy] = kopia;
		sortowanie(tab,lewy,m-1);
		sortowanie(tab,m+1,prawy);
	}
}

void UnorientedIncidenceMatrix::polacz(int x, int y, int *p, int *rank)
{
	link(findSet(x,p), findSet(y,p), p, rank);
}

void UnorientedIncidenceMatrix::link(int x, int y, int *p, int *rank)
{
	if(rank[x] > rank[y])
		p[y] = x;
	else
	{
		p[x] = y;
		if(rank[x] == rank[y])
			rank[y] += 1;
	}
}

int UnorientedIncidenceMatrix::findSet(int x, int *p)
{
	if(x != p[x])
		p[x] = findSet(p[x], p);
	return p[x];
}

UnorientedIncidenceMatrix UnorientedIncidenceMatrix::get_spanning_tree_kruskal (void)
{
    UnorientedIncidenceMatrix tree(nodes,edges);         //Tworzymy macierz drzewa wyjściowego.
    int *p = new int [nodes];							// Potrzebne do wykrycia cykli
    int *rank = new int [nodes];
    // SORTOWANIE KRAWĘDZI WG WAG	
	wagi *krawedzie = new wagi [edges];
	timeval  start_time;
    timeval  finish_time;
    
    gettimeofday (&start_time, NULL);

    // Szukamy wag krawędzi z macierzy incydencji  
    for(int i = 0; i < edges;i++)
    {
		bool drugi = false;
		for(int j = 0; j < nodes; j++)
			{
				if(this->matrix[j][i]!=0)
				{
					if(!drugi)
					{
						krawedzie[i].waga = this->matrix[j][i];
						krawedzie[i].krawedz = i;
						krawedzie[i].wierzcholek_pocz = j;
						drugi = true;
					}
					else
					{
						krawedzie[i].wierzcholek_koniec = j;
						drugi = false;
						break;
					}
				}
			}
	}
	sortowanie(krawedzie,0,edges);
	// for każdy wierzchołek v należący do V[G] do MAKE-SET(v)
	for(int j = 0; j < nodes; j++)
	{
		p[j] = j;
		rank[j] = 0;
	}
	// Dla każdej krawędzi (u,v) należącej do E, w kolejności niemalejących wag:
	for(int i = edges-1; i>=0; i--)
	{
		if(tree.findSet(krawedzie[i].wierzcholek_pocz, p) != tree.findSet(krawedzie[i].wierzcholek_koniec,p))
		{
			// dołączam krawędź
			for(int j = 0; j < nodes; j++)
			{
				tree.matrix[j][krawedzie[i].krawedz] = matrix[j][krawedzie[i].krawedz];
			}
			tree.polacz(krawedzie[i].wierzcholek_pocz, krawedzie[i].wierzcholek_koniec, p, rank);
		}
	}
    
    gettimeofday (&finish_time, NULL);

#ifdef VERBOSE      
    printf ("\tCzas wykonania: %d sekund\n", (finish_time.tv_sec - start_time.tv_sec));
#else
    printf ("%lf\n", (finish_time.tv_sec - start_time.tv_sec) + (finish_time.tv_usec - start_time.tv_usec) / 1000000.0);
#endif // VERBOSE

#ifdef VERBOSE    
	tree.print();
#endif // VERBOSE 	
    delete [] krawedzie;  
    delete [] p;
    delete [] rank;
    return tree;
}

Adjacencylist::Adjacencylist (unsigned int nodes,
                              unsigned int edges) :
    Graph (nodes, edges),
    nodes_vector (nodes)
{
    // ...
}

Adjacencylist::~Adjacencylist (void)
{
    // ...
}

void Adjacencylist::print (void)
{
    unsigned int node (0);
    
    for (node = 0; node < this->nodes; node++)
    {
        NodeNeighboursList&          node_neighbours (this->nodes_vector [node]);
        NodeNeighboursList::iterator neighbour_iterator;
        
        printf ("%2d ", node);
        
        for (neighbour_iterator = node_neighbours.begin (); neighbour_iterator != node_neighbours.end (); neighbour_iterator++)
        {
            Neighbour& neighbour (*neighbour_iterator);
            
            printf ("[%2d,%2d] ", neighbour.node, neighbour.edge_weight);
        }
        
        printf ("\n");
    }
}

bool Adjacencylist::check_nodes (unsigned int begin_node,
                                 unsigned int end_node)
{
    NodeNeighboursList&          begin_node_neighbours (this->nodes_vector [begin_node]); 
    NodeNeighboursList::iterator iterator;
    
    // Nie ma petli zwrotnych
    if (begin_node == end_node)
    {
        return false;
    }
    
    return true;
}

Adjacencylist::Neighbour::Neighbour (unsigned int node,
                                     unsigned int edge_weight) :
    node (node),
    edge_weight (edge_weight)
{
    // ...
}

OrientedAdjacencyList::OrientedAdjacencyList (unsigned int nodes,
                                              unsigned int edges) :
    Adjacencylist (nodes, edges)
{
    // ...
}

void OrientedAdjacencyList::generate (unsigned int minimum_edge_weight,
                                      unsigned int maximum_edge_weight)
{
    mt19937                   engine;
    uniform_int<unsigned int> node_generator (0, this->nodes - 1);
    uniform_int<unsigned int> edge_weight_generator (minimum_edge_weight, maximum_edge_weight);
    unsigned int              edge (0);
    unsigned int              edge_weight (0);
    unsigned int              begin_node (0);
    unsigned int              end_node (0);
    unsigned int              tmp_node (0);
    bool                      status (false);
    
    // Minimanlny graf spojny
    for (tmp_node = 0; tmp_node < this->nodes - 1; tmp_node++)
    {
        NodeNeighboursList& tmp_node_neighbours (this->nodes_vector [tmp_node]);
        
        edge_weight = edge_weight_generator (engine);
        tmp_node_neighbours.push_back (Neighbour (tmp_node + 1, edge_weight));
    }
    
    // Graf spojny
    for (edge = this->nodes - 1; edge < this->edges; edge++)
    {
        // Losujemy poczatkowy wierzcholek i wage krawedzi
        begin_node = node_generator (engine);         
        edge_weight = edge_weight_generator (engine);
        
        do
        {
            end_node = node_generator (engine); 
            status = this->check_nodes (begin_node, end_node);
        } 
        while (status == false);
        
        NodeNeighboursList& begin_node_neighbours (this->nodes_vector [begin_node]);
        
        begin_node_neighbours.push_back (Neighbour (end_node, edge_weight));    
    }
}

void OrientedAdjacencyList::find_shortest_path_dijkstra (unsigned int source_node)
{
    Vector<unsigned int>                  distance (this->nodes);
    Heap<unsigned int, unsigned int>      queue (this->nodes, this->nodes);
    std::pair<unsigned int, unsigned int> current_node;
    unsigned int                          i (0);                   
    timeval                               start_time;
    timeval                               finish_time;
    
    gettimeofday (&start_time, NULL);
    
    // Inicjalizacja struktur
    for (i = 0; i < this->nodes; i++)
    {
        distance [i] = UINT_MAX;
        queue [i].first = UINT_MAX;
        queue [i].second = i;
    }
    
    queue [source_node].first = 0;
    distance [source_node] = 0;
    
    // Wlasciwy algorytm
    while (queue.size () != 0)
    {
        // Znajdz wierzcholek z najnizsza waga     
        current_node = queue.extract_min ();   
        if (current_node.first == UINT_MAX)
        {
            continue;
        }
        
        NodeNeighboursList&          neighbours_list (this->nodes_vector [current_node.second]);
        NodeNeighboursList::iterator neighbour_iterator;
        
        // Aktualizujemy informacje o sciezce do nastepnikow zgodnie z regula relaksacji
        for (neighbour_iterator = neighbours_list.begin (); neighbour_iterator != neighbours_list.end (); neighbour_iterator++)
        {
            Neighbour& neighbour (*neighbour_iterator);
            
            if (distance [neighbour.node] > distance [current_node.second] + neighbour.edge_weight ||
                distance [neighbour.node] == UINTMAX_MAX)
            {
                distance [neighbour.node] = distance [current_node.second] + neighbour.edge_weight;
            }
        }
        
        // Auktualizujemy kolejke
        for (i = 0; i < queue.size (); i++)
        {
            queue.decrease_key (i, distance [queue [i].second]);
        }        

#ifdef VERBOSE        
        // Wyswietl kroki
        for (i = 0; i < this->nodes; i++)
        {
            printf ("%2d ", distance [i]);
        }
              
        printf ("\n");
#endif // VERBOSE         
    }
    
    gettimeofday (&finish_time, NULL);
    
#ifdef VERBOSE      
    printf ("\tCzas wykonania: %d sekund\n", (finish_time.tv_sec - start_time.tv_sec));
#else
    printf ("%lf\n", (finish_time.tv_sec - start_time.tv_sec) + (finish_time.tv_usec - start_time.tv_usec) / 1000000.0);
#endif // VERBOSE
}

void OrientedAdjacencyList::find_shortest_path_bellman_ford (unsigned int source_node)
{
    Vector<unsigned int> distance (this->nodes_vector.size ());
    unsigned int         i (0);
    unsigned int         j (0);
    unsigned int         tmp_node (0);
    unsigned int         tmp_destination_node (0);
    unsigned int         tmp_edge (0);
    unsigned int         u_node (0);
    unsigned int         v_node (0);
    timeval              start_time;
    timeval              finish_time;
    
    gettimeofday (&start_time, NULL);
    
    // Inicjalizacja struktur
    for (i = 0; i < this->nodes_vector.size (); i++)
    {
        distance [i] = UINT_MAX;
    }
    
    distance [source_node] = 0;
    
    for (i = 0; i < this->nodes_vector.size (); i++)
    {
        NodeNeighboursList&          neighbours_list (this->nodes_vector [i]);
        NodeNeighboursList::iterator neighbour_iterator;
        
        for (neighbour_iterator = neighbours_list.begin (); neighbour_iterator != neighbours_list.end (); neighbour_iterator++)
        {
            Neighbour& neighbour (*neighbour_iterator);
            
            // Przeprowadzamy relaksacje
            if ((distance [neighbour.node] > (distance [i] + neighbour.edge_weight)) && distance [i] != -1)
            {
                distance [neighbour.node] = distance [i] + neighbour.edge_weight;
            }
        }
        
#ifdef VERBOSE        
        // Wyswietl kroki
        for (j = 0; j < this->nodes; j++)
        {
            printf ("%2d ", distance [j]);
        }
              
        printf ("\n");
#endif // VERBOSE 
    }
    
    for (i = 0; i < this->nodes_vector.size (); i++)
    {
        NodeNeighboursList&          neighbours_list (this->nodes_vector [i]);
        NodeNeighboursList::iterator neighbour_iterator;
        
        for (neighbour_iterator = neighbours_list.begin (); neighbour_iterator != neighbours_list.end (); neighbour_iterator++)
        {
            Neighbour& neighbour (*neighbour_iterator);
            
            if ((distance [neighbour.node] > (distance [i] + neighbour.edge_weight)) && distance [i] != -1 && distance [neighbour.node] != -1)
            {
#ifdef VERBOSE             
                printf ("Blad\n");
#endif // VERBOSE                
            }
        }
    }
    
    gettimeofday (&finish_time, NULL);
    
#ifdef VERBOSE      
    printf ("\tCzas wykonania: %d sekund\n", (finish_time.tv_sec - start_time.tv_sec));
#else
    printf ("%lf\n", (finish_time.tv_sec - start_time.tv_sec) + (finish_time.tv_usec - start_time.tv_usec) / 1000000.0);
#endif // VERBOSE
}

UnorientedAdjacencyList::UnorientedAdjacencyList (unsigned int nodes,
                                                  unsigned int edges) :
    Adjacencylist (nodes, edges)
{
    // ...
}

void UnorientedAdjacencyList::generate (unsigned int minimum_edge_weight,
                                        unsigned int maximum_edge_weight)
{
    mt19937                                engine;
    uniform_int<unsigned int> node_generator (0, this->nodes - 1);
    uniform_int<unsigned int> edge_weight_generator (minimum_edge_weight, maximum_edge_weight);
    unsigned int                           edge (0);
    unsigned int                           edge_weight (0);
    unsigned int                           begin_node (0);
    unsigned int                           end_node (0);
    unsigned int                           tmp_node (0);
    bool                                   status (false);
    
     // Minimanlny graf spojny
    for (tmp_node = 0; tmp_node < this->nodes - 1; tmp_node++)
    {
        NodeNeighboursList& begin_node_neighbours (this->nodes_vector [tmp_node]);
        NodeNeighboursList& end_node_neighbours (this->nodes_vector [tmp_node+1]);
        
        edge_weight = edge_weight_generator (engine);
        
        begin_node_neighbours.push_back (Neighbour (tmp_node + 1, edge_weight));
        end_node_neighbours.push_back (Neighbour (tmp_node, edge_weight));
    }
    
    // Graf spojny
    for (edge = this->nodes - 1; edge < this->edges; edge++)
    {
        // Losujemy poczatkowy wierzcholek i wage krawedzi
        begin_node = node_generator (engine);         
        edge_weight = edge_weight_generator (engine);
        
        do
        {
            end_node = node_generator (engine); 
            status = this->check_nodes (begin_node, end_node);
        } 
        while (status == false);
        
        NodeNeighboursList& begin_node_neighbours (this->nodes_vector [begin_node]); 
        NodeNeighboursList& end_node_neighbours (this->nodes_vector [end_node]);
        
        begin_node_neighbours.push_back (Neighbour (end_node, edge_weight));
        end_node_neighbours.push_back (Neighbour (begin_node, edge_weight));
    }
}

void UnorientedAdjacencyList::sortowanie(wagi tab[], int lewy, int prawy)
{
if(lewy<prawy)
	{
		int m = lewy;
		for(int i = lewy+1; i <= prawy; i++)
				if(tab[i].waga > tab[lewy].waga)
				{
					wagi kopia;
					kopia = tab[i];
					tab[i] = tab[lewy];
					tab[lewy] = kopia;
				}
		wagi kopia;
		kopia = tab[m];
		tab[m] = tab[lewy];
		tab[lewy] = kopia;
		sortowanie(tab,lewy,m-1);
		sortowanie(tab,m+1,prawy);
	}
}

void UnorientedAdjacencyList::polacz(int x, int y, int *p, int *rank)
{
	link(findSet(x,p), findSet(y,p), p, rank);
}

void UnorientedAdjacencyList::link(int x, int y, int *p, int *rank)
{
	if(rank[x] > rank[y])
		p[y] = x;
	else
	{
		p[x] = y;
		if(rank[x] == rank[y])
			rank[y] += 1;
	}
}

int UnorientedAdjacencyList::findSet(int x, int *p)
{
	if(x != p[x])
		p[x] = findSet(p[x], p);
	return p[x];
}

UnorientedAdjacencyList UnorientedAdjacencyList::get_spanning_tree_prim (void)
{
    UnorientedAdjacencyList wynik(nodes, edges);
	bool *kolejka = new bool [nodes];
    for(int i = 0;i < nodes; i++)
		kolejka[i] = false;
	wagi *krawedzie = new wagi [edges];
	unsigned int node (0);
	int kr = 0;    
	
	timeval  start_time;
    timeval  finish_time;
    
    gettimeofday (&start_time, NULL);
	
	// Wpisujemy do tablicy struktur każdą krawędź. Eliminujemy krawędzie powtarzające się.
    for (node = 0; node < this->nodes; node++)
    {
        NodeNeighboursList&          node_neighbours (this->nodes_vector [node]);
        NodeNeighboursList::iterator neighbour_iterator;
        
        for (neighbour_iterator = node_neighbours.begin (); neighbour_iterator != node_neighbours.end (); neighbour_iterator++)
        {
            Neighbour& neighbour (*neighbour_iterator);
            if(node < neighbour.node)
            {
				krawedzie[kr].wierzcholek_pocz = node;
				krawedzie[kr].wierzcholek_koniec = neighbour.node;
				krawedzie[kr].krawedz = kr;
				krawedzie[kr].waga = neighbour.edge_weight;
				kr++;
			}
        }
    }
	sortowanie(krawedzie,0,edges);
	int *korzen = new int [nodes];
	int *nastepny = new int [nodes];
	for(int i = 0;i<nodes;i++)
	{
		korzen[i] = nastepny[i] = i;
	}
	kolejka[krawedzie[0].wierzcholek_pocz] = true;
	kolejka[krawedzie[0].wierzcholek_koniec] = true;
	for(int i = 0; i < nodes-1; i++)
	{
		for(int j = edges-1; j>=0;j--)
		{
			if((korzen[krawedzie[j].wierzcholek_pocz] != korzen[krawedzie[j].wierzcholek_koniec]) &&
				(kolejka[krawedzie[j].wierzcholek_pocz] || kolejka[krawedzie[j].wierzcholek_koniec]))
				{
					int temp;
					int pomoc = korzen[krawedzie[j].wierzcholek_pocz];
					korzen[pomoc] = korzen[krawedzie[j].wierzcholek_koniec];
					for(int k = nastepny[pomoc];k!=pomoc;k=nastepny[k])
					{
						korzen[k] = korzen[krawedzie[j].wierzcholek_koniec];
					}
					temp = nastepny[pomoc];
					nastepny[pomoc] = nastepny[korzen[krawedzie[j].wierzcholek_koniec]];
					nastepny[korzen[krawedzie[j].wierzcholek_koniec]] = temp;
					//dodajkraw
					#ifdef VERBOSE
					NodeNeighboursList& begin_node_neighbours (wynik.nodes_vector [krawedzie[j].wierzcholek_pocz]); 
					NodeNeighboursList& end_node_neighbours (wynik.nodes_vector [krawedzie[j].wierzcholek_koniec]);
					begin_node_neighbours.push_back (Neighbour (krawedzie[j].wierzcholek_koniec, krawedzie[j].waga));
					end_node_neighbours.push_back (Neighbour (krawedzie[j].wierzcholek_pocz, krawedzie[j].waga));
					#endif //VERBOSE
					
					kolejka[krawedzie[j].wierzcholek_pocz] = true;
					kolejka[krawedzie[j].wierzcholek_koniec] = true;
					break;
				}
		}
	}
	gettimeofday (&finish_time, NULL);

#ifdef VERBOSE    
    printf ("\tCzas wykonania: %d sekund\n", (finish_time.tv_sec - start_time.tv_sec));
#else
    printf ("%lf\n", (finish_time.tv_sec - start_time.tv_sec) + (finish_time.tv_usec - start_time.tv_usec) / 1000000.0);
#endif // VERBOSE

#ifdef VERBOSE 	
	wynik.print();
	printf("\n");
#endif // VERBOSE
	delete [] kolejka;
	//delete [] krawedzie;
	return wynik;
}

UnorientedAdjacencyList UnorientedAdjacencyList::get_spanning_tree_kruskal (void)
{
	UnorientedAdjacencyList wynik(nodes, edges);
	int *p = new int [nodes];
	int *rank = new int [nodes];
	wagi *krawedzie = new wagi [edges];
    unsigned int node (0);
    int kr = 0;    
    timeval  start_time;
    timeval  finish_time;
    
    gettimeofday (&start_time, NULL);
    
    // Wpisujemy do tablicy struktur każdą krawędź. Eliminujemy krawędzie powtarzające się.
    for (node = 0; node < this->nodes; node++)
    {
        NodeNeighboursList&          node_neighbours (this->nodes_vector [node]);
        NodeNeighboursList::iterator neighbour_iterator;
        
        for (neighbour_iterator = node_neighbours.begin (); neighbour_iterator != node_neighbours.end (); neighbour_iterator++)
        {
            Neighbour& neighbour (*neighbour_iterator);
            if(node < neighbour.node)
            {
				krawedzie[kr].wierzcholek_pocz = node;
				krawedzie[kr].wierzcholek_koniec = neighbour.node;
				krawedzie[kr].krawedz = kr;
				krawedzie[kr].waga = neighbour.edge_weight;
				kr++;
			}
        }
    }
	sortowanie(krawedzie,0,edges);
	// for każdy wierzchołek v należący do V[G] do MAKE-SET(v)
	for(int j = 0; j < nodes; j++)
	{
		p[j] = j;
		rank[j] = 0;
	}
	// Dla każdej krawędzi (u,v) należącej do E, w kolejności niemalejących wag:
	for(int i = edges-1; i>=0; i--)
	{
		if(wynik.findSet(krawedzie[i].wierzcholek_pocz, p) != wynik.findSet(krawedzie[i].wierzcholek_koniec,p))
		{
			NodeNeighboursList& begin_node_neighbours (wynik.nodes_vector [krawedzie[i].wierzcholek_pocz]); 
			NodeNeighboursList& end_node_neighbours (wynik.nodes_vector [krawedzie[i].wierzcholek_koniec]);
        
			begin_node_neighbours.push_back (Neighbour (krawedzie[i].wierzcholek_koniec, krawedzie[i].waga));
			end_node_neighbours.push_back (Neighbour (krawedzie[i].wierzcholek_pocz, krawedzie[i].waga));
			wynik.polacz(krawedzie[i].wierzcholek_pocz, krawedzie[i].wierzcholek_koniec, p, rank);
		}
	}	
    
    gettimeofday (&finish_time, NULL);

#ifdef VERBOSE    
    printf ("\tCzas wykonania: %d sekund\n", (finish_time.tv_sec - start_time.tv_sec));
#else
    printf ("%lf\n", (finish_time.tv_sec - start_time.tv_sec) + (finish_time.tv_usec - start_time.tv_usec) / 1000000.0);
#endif // VERBOSE

#ifdef VERBOSE 	
	wynik.print();
	printf("\n");
#endif // VERBOSE 
    delete [] p;
    delete [] rank;
    //delete [] krawedzie;
    return wynik;
}
